package 数据结构练习.summer;

import java.util.ArrayList;
import java.util.List;

public class day14 {
    /*
    给你一个目标数组 target 和一个整数 n。每次迭代，需要从 list = {1,2,3..., n} 中依序读取一个数字。
    请使用下述操作来构建目标数组 target ：
    Push：从 list 中读取一个新元素， 并将其推入数组中。
    Pop：删除数组中的最后一个元素。
    如果目标数组构建完成，就停止读取更多元素。
    题目数据保证目标数组严格递增，并且只包含 1 到 n 之间的数字。
    请返回构建目标数组所用的操作序列。
    题目数据保证答案是唯一的。
    https://leetcode.cn/problems/build-an-array-with-stack-operations
     */
    public List<String> buildArray(int[] target, int n) {
        ArrayList<String> iu = new ArrayList<>();
        int i = 0;
        for (int j = 1; j <= n; j++) {
            if (target[i] == j) {
                iu.add("Push");
                i++;
            } else {
                iu.add("Push");
                iu.add("Pop");
            }
            if (i == target.length) return iu;
        }
        return iu;
    }


    /*
    nums1中数字x的 下一个更大元素 是指x在nums2 中对应位置 右侧 的 第一个 比x大的元素。
    给你两个 没有重复元素 的数组nums1 和nums2 ，下标从 0 开始计数，其中nums1是nums2的子集。
    对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在
    nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。
    返回一个长度为nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。
    https://leetcode.cn/problems/next-greater-element-i
     */
    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int temp = 0;
        int[] ans = new int[nums1.length];
        int index = 0;
        boolean flag = false;
        for (int i = 0; i < nums1.length; i++) {
            temp = nums1[i];
            for (int j = 0; j < nums2.length; j++) {
                if (nums1[i] == nums2[j]) {
                    flag = true;
                }
                if (flag) {
                    if (nums2[j] > temp) {
                        temp = nums2[j];
                        flag = false;
                    }
                }
            }
            flag = false;
            if (temp == nums1[i]) {
                ans[index++] = -1;
            } else {
                ans[index++] = temp;
            }
        }
        return ans;
    }
}
